package Stream;

public class Salution2 {
        public int countPrimes(int n) {
            if (n <= 2) {
                return 0;  // 小于 2 的数没有质数
            }

            boolean[] isPrime = new boolean[n];

            // 默认所有数都是质数
            for (int i = 2; i < n; i++) {
                isPrime[i] = true;
            }

            // 筛选出质数
            for (int i = 2; i * i < n; i++) {
                if (isPrime[i]) {
                    // 将 i 的倍数标记为合数
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }

            // 统计质数的数量
            int count = 0;
            for (int i = 2; i < n; i++) {
                if (isPrime[i]) {
                    count++;
                }
            }

            return count;
        }
    }

